package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description: 380. O(1) 时间插入、删除和获取随机元素
 *
 * @author weiruibai.vendor
 * Date: 2022/7/20 09:55
 */
public class Solution_280 {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(80);
        list.remove(1);

//        test();
        RandomizedSet randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.insert(1)); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
        System.out.println(randomizedSet.remove(2)); // 返回 false ，表示集合中不存在 2 。
        System.out.println(randomizedSet.insert(2)); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
        System.out.println(randomizedSet.getRandom()); // getRandom 应随机返回 1 或 2 。
        System.out.println(randomizedSet.remove(1)); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
        System.out.println(randomizedSet.insert(2)); // 2 已在集合中，所以返回 false 。
        System.out.println(randomizedSet.getRandom()); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。


        // ======

        randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.insert(3));
        System.out.println(randomizedSet.insert(4));
        System.out.println(randomizedSet.insert(5));
        System.out.println(randomizedSet.insert(10));
        System.out.println(randomizedSet.remove(4));
        System.out.println(randomizedSet.insert(2));
        System.out.println(randomizedSet.remove(1));
        System.out.println(randomizedSet.getRandom());
        /**
         * ["RandomizedSet","insert","insert","remove","insert","remove","getRandom"]
         * [[],[0],[1],[0],[2],[1],[]]
         */
        randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.insert(0));
        System.out.println(randomizedSet.insert(1));
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.insert(2));
        System.out.println(randomizedSet.remove(1));
        System.out.println(randomizedSet.getRandom());
    }

    /**
     * 测试如何把一定长度的平均分配到数组中
     */
    private static void test() {
        int times = 10000000;
        int length = 10;
        int[] arr = new int[length];
        for (int i = 0; i < times; i++) {
            int index = (int) (Math.random() * length);
            if (index >= 0 && index < 10) {
                arr[index]++;
            } else {
                System.out.println("漏网：i=" + index);
            }
        }
        for (int i = 0; i < length; i++) {
            System.out.println("i=" + i + "," + (double) arr[i] / (double) times);
        }

    }

}

class RandomizedSet {

    Map<Integer, Integer> indexMap;
    List<Integer> list;

    public RandomizedSet() {
        list = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    public boolean insert(int val) {
        if (list.contains(val)) {
            return false;
        }
        int size = list.size();
        list.add(size, val);
        indexMap.put(val, size);
        return true;
    }

    /**
     * 重点在如何把移除的值正确更新索引！！
     * 思路：
     * 假设：list={1,2,3,4,5},则indexMap={1:0,2:1,3:2,4:3,5:4}
     * 当移除3时
     * 1、把val=3在数组中的位置从indexMap中拿出来为：2
     * 2、把list中最后的值拿出来：5
     * 3、把最后一个值的位置更新到要移除val的位置中，更新后为：list={1,2,5,4,5},indexMap={1:0,2:1,3:2,4:3,5:2}
     * 4、移除list的最后一个位置元素为：list={1,2,5,4},indexMap移除值val=3的元素: indexMap={1:0,2:1,4:3,5:2}
     *
     * @param val
     * @return
     */
    public boolean remove(int val) {
        if (!list.contains(val)) {
            return false;
        }
        // 获取val在list中的位置
        int index = indexMap.get(val);
        int size = list.size();
        // 获取数组的最后的数
        int lastVal = list.get(size - 1);
        // 把最后一个位置的值移动到index位置
        indexMap.put(lastVal, index);
        list.set(index, lastVal);
        // 移除最后一个数
        list.remove(size - 1);
        indexMap.remove(val);
        return true;
    }

    public int getRandom() {
        int size = list.size();
        int index = (int) (Math.random() * size);
        return list.get(index);
    }
}

